Graph valid tree

Time: O(|V|+|E|); Space: O(|V|+|E|); medium

Given N nodes labeled from 0 to N - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Have you met this question in a real interview?

Example 1:

Input: n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]

Output: True

Example 2:

Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]

Output: False

from collections import defaultdict, deque

class Solution1:
    """
    BFS solution. Same complexity but faster version.
    Time:  O(|V| + |E|)
    Space: O(|V| + |E|)
    """
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        if len(edges) != n - 1:  # Check number of edges.
            return False
        elif n == 1:
            return True

        # A structure to track each node's [visited_from, neighbors]
        visited_from = [-1] * n
        neighbors = defaultdict(list)
        for u, v in edges:
            neighbors[u].append(v)
            neighbors[v].append(u)

        if len(neighbors) != n:  # Check number of nodes.
            return False

        # BFS to check whether the graph is valid tree.
        visited = {}
        q = deque([0])
        while q:
            i = q.popleft()
            visited[i] = True
            for node in neighbors[i]:
                if node != visited_from[i]:
                    if node in visited:
                        return False
                    else:
                        visited[node] = True
                        visited_from[node] = i
                        q.append(node)
        return len(visited) == n

s = Solution1()
n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
assert s.validTree(n, edges) == True
n = 5
edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
assert s.validTree(n, edges) == False

from collections import defaultdict, deque

class Solution2:
    '''
    BFS solution.
    Time:  O(|V| + |E|)
    Space: O(|V| + |E|)
    '''
    # @param {integer} n
    # @param {integer[][]} edges
    # @return {boolean}
    def validTree(self, n, edges):
        # A structure to track each node's [visited_from, neighbors]
        visited_from = [-1] * n
        neighbors = defaultdict(list)
        for u, v in edges:
            neighbors[u].append(v)
            neighbors[v].append(u)

        # BFS to check whether the graph is valid tree.
        visited = {}
        q = deque([0])
        while q:
            i = q.popleft()
            visited[i] = True
            for node in neighbors[i]:
                if node != visited_from[i]:
                    if node in visited:
                        return False
                    else:
                        visited[node] = True
                        visited_from[node] = i
                        q.append(node)
        return len(visited) == n

s = Solution2()
n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
assert s.validTree(n, edges) == True
n = 5
edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
assert s.validTree(n, edges) == False

See also:

https://leetcode.com/problems/graph-valid-tree

https://www.lintcode.com/problem/graph-valid-tree